#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define in read<int>()
#define lin read<ll>()
#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using ll = long long;
using db = double;
using pii = pair < int, int >;
using vec = vector < int >;
using veg = vector < pii >;

template < typename T > T read() {
	T x = 0; bool f = 0; char ch = getchar();
	while(!isdigit(ch)) f |= ch == '-', ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

template < typename T > void chkmax(T &x, const T &y) { x = x > y ? x : y; }
template < typename T > void chkmin(T &x, const T &y) { x = x < y ? x : y; }

const int N = 4010;
const int mod = 1e9 + 7;

int p, alp, la, lx, x[N];
char a[N];
int f[N][N][2][2];

void upd(int &x) { x = x + (x >> 31 & mod); }

void trans() {
	rep(i, 1, la) a[i] -= '0'; reverse(a + 1, a + la + 1);
	while(la) {
		ll res = 0; per(i, la, 1) { res = res * 10 + a[i]; a[i] = res / p; res %= p; if(i == la && a[i] == 0) la--; }
		x[++lx] = res;
	} reverse(x + 1, x + lx + 1); // high -> low.
}

int tcalc(int f, int s) { return f > s ? 0 : 1ll * (f + s) * (s - f + 1) / 2 % mod; }

int calc(int x) {
	chkmin(x, 2 * p - 2); if(x < p) return 1ll * (x + 2) * (x + 1) / 2 % mod; 
	return (1ll * (x - p + 2) * p % mod + tcalc(x - p + 2, p - 1)) % mod; 
}

int calc(int l, int r) { chkmax(l, 0); chkmin(r, 2 * p - 2); return l > r ? 0 : (calc(r) - (l == 0 ? 0 : calc(l - 1)) + mod) % mod; }

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
#endif
	p = in, alp = in; scanf("%s", a + 1); la = strlen(a + 1);
	trans(); if(alp > lx) return puts("0"), 0; f[1][alp][1][0] = 1;
	rep(i, 1, lx) rep(j, 0, alp) rep(lim, 0, 1) rep(nd, 0, 1)
		if(f[i][j][lim][nd]) {
			if(lim) {
				if(nd) {
					upd(f[i + 1][max(j - 1, 0)][0][0] += 1ll * f[i][j][lim][nd] * calc(p, p + x[i] - 1) % mod - mod);
					upd(f[i + 1][max(j - 1, 0)][1][0] += 1ll * f[i][j][lim][nd] * calc(p + x[i], p + x[i]) % mod - mod);
					
					upd(f[i + 1][max(j - 1, 0)][0][1] += 1ll * f[i][j][lim][nd] * calc(p - 1, p + x[i] - 2) % mod - mod);
					upd(f[i + 1][max(j - 1, 0)][1][1] += 1ll * f[i][j][lim][nd] * calc(p + x[i] - 1, p + x[i] - 1) % mod - mod);
				} else {
					upd(f[i + 1][j][0][0] += 1ll * f[i][j][lim][nd] * calc(0, x[i] - 1) % mod - mod);
					upd(f[i + 1][j][1][0] += 1ll * f[i][j][lim][nd] * calc(x[i], x[i]) % mod - mod);
					
					upd(f[i + 1][j][0][1] += 1ll * f[i][j][lim][nd] * calc(0, x[i] - 2) % mod - mod);
					upd(f[i + 1][j][1][1] += 1ll * f[i][j][lim][nd] * calc(x[i] - 1, x[i] - 1) % mod - mod);
				}
			} else {
				if(nd) {
					upd(f[i + 1][max(j - 1, 0)][0][0] += 1ll * f[i][j][lim][nd] * calc(p, 2 * p - 1) % mod - mod);
					upd(f[i + 1][max(j - 1, 0)][0][1] += 1ll * f[i][j][lim][nd] * calc(p - 1, 2 * p - 2) % mod - mod);
				} else {
					upd(f[i + 1][j][0][0] += 1ll * f[i][j][lim][nd] * calc(0, p - 1) % mod - mod);
					upd(f[i + 1][j][0][1] += 1ll * f[i][j][lim][nd] * calc(0, p - 2) % mod - mod);
				}
			}
		}
	printf("%d\n", (f[lx + 1][0][0][0] + f[lx + 1][0][1][0]) % mod);
	return 0;
}
